分组密码算法能量分析攻击中效率与容错问题研究

【摘要】分组密码是目前应用最为广泛的密码体制之一,它是一类对称密码算法,使用同一密钥进行加密和解密运算。本质上,分组密码是一种带密钥的置换,它将明文数据划分为多个长度相等的分组,并转换为相同长度的密文。目前主流的分组密码算法在数学结构方面具有较高的安全性,很难被数学分析的方法破解。然而,数学分析方法主要针对明文和密文进行分析,在算法通过密码设备实现的安全性分析方面具有一定局限性。自从1996年Kocher提出了研究操作时间的计时攻击以来[1],侧信道攻击及防御逐渐成为密码学的一个重要分支。有别于传统的暴力破解,或者针对密码理论的弱点进行研究,侧信道攻击分析密码算法物理实现过程中某些中间值泄露的信息,从而获取密钥。时间、电磁波、乃至声音等信息均可以作为攻击密码系统的侧信道信息,除此之外,能量消耗分析是侧信道攻击最有效的手段之一。在实际应用中,这些攻击通常会借助密码芯片,如微处理器、FPGA(Field-ProgrammableGateArray)、ASIC(ApplicationSpecificIntegratedCircuit)[2]等来实现。1999年,Kocher等人提出了能量分析攻击[3,4],这种攻击能够通过密码芯片执行过程中的瞬时能量消耗来获取中间值信息,从而推导出密钥。之后Chari等人于2002年提出了模板攻击[5]。模板攻击根据密码设备泄露的信息数据以及相关操作的特征来构建模板,寻找与获取的信息最匹配的模板,从而有效缩小密钥搜索空间。2004年,Brier等人提出了相关能量分析,这种攻击建立在差分能量分析的基础上,采用相关系数模型来恢复密钥[6]。本文重点研究针对分组密码算法的能量分析攻击,以AES(AdvancedEncryptionStandard)算法为例,提出了比现有攻击方法更为有效的容错线性碰撞攻击和基于二阶距离的比特碰撞攻击。并使用比特碰撞攻击改进容错线性碰撞攻击,进而得到容错比特碰撞攻击。最后针对几种经典算法的S盒结构,进行了相关能量分析、模板攻击、以及比特碰撞攻击的效率研究。1.容错线性碰撞攻击相关能量分析[6]和碰撞攻击都是常见的能量分析攻击方法。Bogdanov等人将相关能量分析与碰撞攻击结合,提出了测试链的概念[7],并指出这种方法的攻击效率高于独立的相关能量分析或碰撞攻击。然而,测试链攻击只能纠正相关能量分析部分出现的错误,对碰撞攻击部分出现的错误无能为力。换句话说,一旦在测试链的一条路径中出现错误,它将导致随后连续出现错误,乃至整条路径错误,造成攻击失败。并且由于实际上碰撞攻击的效率低于相关能量分析,这使得Bogdanov等人的方法可能不切实际。我们以测试链思想为基础,提出了容错链的概念。以AES第一个密钥字节k1为例,容错链选取k1作为唯一的自由变量,即从k1出发,通过碰撞攻击构造k1与其它15个密钥字节之间的关系ki(?)ki=△1.i(2≤i≤16).(1)这15个关系式相互独立,因此如果一个关系式出错,其错误结果不会影响其它关系式。在攻击的具体实现中我们采用相关强化碰撞攻击构造容错链。在容错线性碰撞攻击中,我们不仅构造一个容错链,同时还采用相关能量分析对密钥候选值进行排序,并给定一个阈值ThCPA’筛选出每个密钥字节的候选值集合。满足容错链关系式(1)且属于密钥候选集合的密钥,可以判定为正确密钥。由于除k1外的其它密钥字节互不影响,因此可以给定一个碰撞攻击部分的阈值ThCA’使得攻击成功返回的密钥可以包含至多ThCA个错误的字节。随后通过少量搜索能够找到正确的密钥。我们通过仿真实验对容错线性碰撞攻击和测试链攻击进行了效率比对。实验结果表明,当两种攻击的成功率均在90%以上时,容错线性碰撞攻击所需能量迹数量少于测试链攻击。为了进一步缩小密钥搜索空间,我们给出一个纠错机制,能够较为精确的识别错误密钥字节的位置。随后讨论了错误发生在相关能量分析部分和碰撞攻击部分的可能性,并通过实验给出了ThCPA的取值范围。最后我们分析了ThcpA的取值对攻击成功率的影响,根据实验数据建议ThCPA=10为最有效取值。2.基于二阶距离的比特碰撞攻击2010年,Moradi等人提出了针对AES硬件实现的相关强化碰撞攻击。然而,他们的攻击方法在实际操作中存在效率问题。相关强化碰撞攻击按字节进行操作,因此每次攻击至少需要256条平均能量迹。攻击者需要在示波器上对采集的原始能量迹进行平均,然后手动存储；或者将大量原始能量迹存储到计算机中,再使用MATLAB进行平均。其中采集、存储、以及平均能量迹的过程极为繁琐且耗费时间。攻击者通常希望攻击实现尽可能快速有效,我们以此为出发点提出了较为灵活的基于二阶距离的比特碰撞攻击,它使用能量迹距离模型和逐比特比较的思想区分碰撞。以AES算法为例,选定一个全零明文P0和8个特殊明文Pα(α=1,2,..,8),每个Pα包含16个同样的字节pα,其第α比特为1,其它比特为0。Pα与密钥进行异或运算得到S盒的输入值,每个S盒的输入值即为第α比特发生变化的密钥字节,并且运算前后的汉明重量也随之变化。由于输入P0不会引发任何比特改变,因此输入Pα后,通过比较不同S盒输入值的汉明重量之差是否与输入P0相同,可以推断对应的密钥字节的第α比特是否相等。以P0和P1为例,令ΔHW0和ΔHW1分别表示选择P0或P1前两个S盒输入值汉明重量的差值,可以通过条件(2)和(3)判断k1和k2第一个比特u1和v1是否相等。●当且仅当u1=v1时,|△HW°-△HW1|=O.(2)●当且仅当u1≠v1时,|△HW°-△HW1|=2.(3)在实际攻击中,我们使用能量迹距离模型逼近汉明重量模型,因此可以成功区分出碰撞和非碰撞。本文还给出另外一个距离模型。如果用ΔHW0和ΔHW1表示汉明重量之和,即一阶距离的减法运算替换为加法运算,而二阶距离保持不变,此时同样可以实现比特碰撞攻击。其碰撞与否与上述结论(2)和(3)恰好相反。我们对比特碰撞攻击进行了实际操作和仿真实验。在实际操作中给出了差分能量迹和二阶距离的比较图示,证明比特碰撞攻击切实有效。仿真实验分别研究了能量迹数量、操作时间以及采样点数量等指标,对比特碰撞攻击与相关强化碰撞攻击进行了效率比对。由实验数据得知,比特碰撞攻击优于相关强化碰撞攻击,尤其在实际操作中,前者所需时间仅为后者的8%。由于比特碰撞攻击与相关强化碰撞攻击的返回结果均为密钥字节的异或值,而前者效率更高,因此我们使用比特碰撞攻击构造容错链,完成容错线性碰撞攻击中的碰撞攻击部分。改进后的攻击称之为容错比特碰撞攻击。通过实验数据可知,容错比特碰撞攻击的攻击效率高于容错线性碰撞攻击。3.S盒位宽与能量分析攻击效率的关系研究数据加密标准DES(DataEncryptionStandard)于1976年被美国联邦政府的国家标准局确定为联邦资料处理标准[9，10],其安全性依赖于破解算法的计算难度大和计算时间长。随着计算机与网络技术的发展,目前所拥有的计算能力已经对DES造成了威胁。1997年,美国国家标准和技术研究所发起征集高级加密标准AES的活动,并于2000年确定了Rijndael算法为AES。Serpent算法也是AES的候选算法之一[11]。目前分组密码的设计主要关注于非线性S盒、置换方法以及密钥扩展方案。S盒首次出现于Lucifer算法中,由于DES的深远影响而被广泛应用。S盒是许多分组密码算法中唯一的非线性部件,因此算法的安全强度很大程度上取决于S盒的安全强度。在一轮运算中,DES使用8个S盒,输入6比特输出4比特；AES使用16个S盒,输入输出均为8比特；Serpent使用32个S盒,输入输出均为4比特。由于实验中使用的AES和Serpent的分组长度为128比特,而DES为64比特,为合理比较攻击效率,我们假设一个DES的扩展结构DES-E,其数据长度为128比特,且一轮使用16个DES结构的S盒。我们在相同的实验环境下研究三种能量分析攻击方法针对一轮加密算法中单个S盒的攻击效率。假设一轮攻击的成功率高于50%,可以推出：DES单个S盒的成功率应达到0.9170,DES-E和AES单个S盒的成功率应达到0.9576,Serpent单个S盒的成功率应达到0.9786。在相关能量分析中,S盒打乱了数据的线性规律,其输出值能更好的体现数据相关性,因此选取S盒的输出值作为攻击对象。由于计算相关系数需要多条能量迹,因此每条能量迹上选取1个采样点即可实现攻击。由实验数据得知,达到期望成功率针对Serpent所需能量迹数量最多,其抗攻击性最强。AES抗攻击性最弱,低位宽S盒的安全强度高于高位宽S盒。在模板攻击中,由于构建模板需要知道精确的汉明重量,因此选取S盒的输入值作为攻击对象。为了较为精确的匹配模板,我们使用简化模板攻击方法并选取10个采样点。由实验数据得知,此时AES抗攻击性最强,DES最弱。在基于二阶距离的比特碰撞攻击中,由于攻击思想也依赖于中间值具体的汉明重量,因此选取S盒的输入值作为攻击对象。为了衡量能量迹间距离,每条能量迹选取10个采样点。由实验数据得知,此时AES抗攻击性最强,Serpent最弱,高位宽S盒的安全强度高于低位宽S盒。因此,在不同的能量分析攻击下,不同结构的S盒抗攻击性各有优劣。算法的设计可以酌情考虑在不同攻击方法下S盒的安全强度,以满足特定需求。
【作者】王丹辉；
【导师】王小云；
【作者基本信息】山东大学，信息安全，2014，博士
【关键词】分组密码；能量分析攻击；碰撞攻击；容错攻击；效率分析；S盒；

【参考文献】
[1]张丽春.人类基因的专利问题研究[D].华东政法学院,法律,2003,硕士.
[2]李晓菡.传统与现代的激荡[D].中国音乐学院,音乐学,2014,硕士.
[3]余地.论儒家“仁爱”思想对罪犯人权意识的提升[D].苏州大学,法律（专业学位）,2013,硕士.
[4]曲宁.酒石酸泰乐菌素颗粒质量研究[D].山东大学,制药工程（专业学位）,2013,硕士.
[5]王升琼.UAProf在3G业务中的作用[J].电信网技术.2005(03)
[6]朱志刚.在初中思想品德课教学中实施“自主合作探究”学习方式的研究[D].华中师范大学,学科教育,2014,硕士.
[7]杨亚坤.垂体ACTH腺瘤全转录组深度测序及患者临床表型—基因型关联分析研究[D].北京协和医学院,神经外科（专业学位）,2014,博士.
[8]樊龙飞.天然气/柴油双燃料发动机喷油泵供油量分析[D].长安大学,载运工具运用工程,2013,硕士.
[9]温春宇.乳化纳米铁降解硝基苯污染地下水的研究[D].吉林大学,环境工程,2014,硕士.
[10]陈桂英.基于MEMS矢量水听器阵列的测向技术研究[D].中北大学,测试计量技术及仪器,2014,硕士.
[11]顾冉.分布式以太网交换机体系结构的研究[D].西安电子科技大学,计算机应用技术,2004,硕士.
[12]郭程程.基于网络控制系统环境的系统辨识算法研究[D].大连理工大学,控制理论与控制工程,2013,硕士.
[13]刘萱萱.哲学视域中的文化软实力研究[D].四川外国语大学,外国哲学,2014,硕士.
[14]乾栋梁.静止性脑梗死患者认知障碍的研究[D].兰州大学,神经病学,2013,硕士.
[15]刘昊苏,雷俊卿.矮塔斜拉桥上部结构构件刚度敏感性研究[J].北京交通大学学报,2014,04:122-127.
[16]祝红钗.里氏拟石磺线粒体基因组及石磺科四属种贝类转录组分析[D].上海海洋大学,海洋生物学,2013,硕士.
[17]刘川.手机视频播放系统的研究与实现[D].北京邮电大学,计算机科学与技术,2013,硕士.
[18]石丰祥.多塔斜拉桥施工关键技术研究[D].北京交通大学,桥梁与隧道,2013,硕士.
[19]钟琦.氨基酰化酶法拆分制备手性氨基酸[D].浙江大学,生物化学工程,2004,硕士.
[20]尤鑫.农村女性家庭权力变迁背景下家庭养老资源供给研究[D].华中农业大学,社会保障,2014,硕士.
[21]徐承伟.关于Fuzzy调节器的积分作用[J].自动化学报,1985,02:198-201.
[22]赵巍.微网综合控制技术研究[D].南京理工大学,电力系统及其自动化,2013,硕士.
[23]刘丽花.中华绒螯蟹副性腺分泌蛋白鉴定及一种丝氨酸蛋白酶抑制剂功能研究[D].华东师范大学,动物学,2013,硕士.
[24]李德军,莫江明,方运霆,李志安.模拟氮沉降对南亚热带两种乔木幼苗生物量及其分配的影响[J].植物生态学报,2005,04:543-549.
[25]张航.高职高专公共英语教材：《21世纪大学实用英语第一册》与《新职业英语1》对比分析与研究[D].内蒙古师范大学,课程与教学论,2013,硕士.
[26]张添.基于Selenium的Web自动化测试[D].北京交通大学,2014.
[27]和建政.青海沙蜥低氧习服和适应的不同调节机制及低氧对荒漠沙蜥体温调节和静止代谢率的影响[D].兰州大学,生物化学与分子生物学,2013,硕士.
[28]张腾.PES-C-g-PA6接枝共聚物的制备及其对PES-C、PES-C/PA6体系的改性研究[D].华侨大学,材料物理与化学,2013,硕士.
[29]闫鹏程.Mg_xZn_(1-x)O合金材料的制备与光学性质研究[D].大连理工大学,化学工艺,2013,硕士.
[30]张静.基于文本类型理论的产品简介汉英翻译策略研究[D].江西财经大学,英语语言文学,2013,硕士.
[31]苗永禄.基于视频图像处理的车辆检测与跟踪方法研究[D].长安大学,载运工具运用工程,2014,硕士.
[32]廖素环.广西流行猪瘟病毒E_2基因序列测定及分析[D].广西大学,预防兽医学,2003,硕士.
[33]郑贝贝.冯雪峰寓言研究[D].西北大学,中国现当代文学,2013,硕士.
[34]傅颖.企业微博营销对消费者购买意愿的影响研究[D].浙江工商大学,企业管理,2013,硕士.
[35]郑美凤.有限需求信息下的间断需求预测及库存控制研究[D].上海大学,企业管理,2012,硕士.
[36]周毅博.价值链模块化背景下我国产业升级研究[D].郑州大学,西方经济学,2013,硕士.
[37]杨琪.消费文化语境中的热播抗日题材电视剧研究[D].苏州大学,传播学（专业学位）,2014,硕士.
[38]李咏.两种Broadcom机顶盒方案的软硬件研发[D].天津大学,信号与信息处理,2004,硕士.
[39]陈书平.CGZ公司股权投资结构优化管理的实证研究[D].四川大学,工商管理,2003,硕士.
[40]温江杨.组织胺对T细胞作用的初步实验研究[D].山西医科大学,免疫学,2003,硕士.
[41]李晓杰.货币政策中介指标与商业银行经营策略研究[D].山西财经大学,金融学,2013,硕士.
[42]刘哲.鄂尔多斯盆地上古生界天然气输导体系研究[D].西北大学,矿产普查与勘探,2013,硕士.
[43]刘东音子.深圳市福田区儿童社会音乐教育现状调查与对策研究[D].华中师范大学,教育管理,2013,硕士.
[44]张福俊.图书馆资源数字化建设及应用研究[D].山东科技大学,2005.
[45]郭丽丹.《人民日报》关于H7N9禽流感的报道研究[D].河北大学,新闻与传播,2014,硕士.
[46]董海军.莫里青油田低渗透储层实验地质分析研究[D].东北石油大学,地质工程（专业学位）,2013,硕士.
[47]白鸽.黑龙江绿色食品标准化基地建设研究[D].东北农业大学,农村与区域发展（专业学位）,2013,硕士.
[48]刘晓玲.准备车间—中煤仓黄土边坡变形破坏机制与稳定研究[D].西安科技大学,地质工程,2014,硕士.
[49]孙青峰.基于空间句法分析的城市商业街区空间建构研究[D].北方工业大学,建筑设计及其理论,2014,硕士.
[50]杜婧.子女生命事件对农村留守老人社会支持的影响探析[D].首都师范大学,课程与教学论,2014,硕士.